package tep;

public class ch4 {

    //归并排序

    public static void sort(int[] arr){
        int len = arr.length;
        int [] dst = new int[len];
        for(int i=0; i<len; i++){
            dst[i] = arr[i];
        }

        merge(dst,arr,0,len);



    }

    private static void merge(int[] dst, int[] arr, int i, int len) {
        if((i+1)>=len) return;
        int mid = (i+len)/2;
        merge(arr, dst, i, mid);
        merge(arr, dst, mid, len);

        int left = i;
        int right = mid;
        int index = i;
        while(left<mid && right<len){
            if(dst[left]<dst[right]){
                arr[index] = dst[left];
                index++;
                left++;
            }else {
                arr[index] = dst[right];
                index++;
                right++;
            }
        }

        for (int j=left; j<mid; j++){
            arr[index] = dst[j];
            index++;
        }
        for (int j=right; j<len; j++){
            arr[index] = dst[j];
            index++;
        }


    }


    public static void main(String[] args) {
        int[] arr = new int[]{2,1,4,5,5,1,10,9};
        sort(arr);
        System.out.println(" ");
        for (int i:arr){
            System.out.print(i+" ");
        }

    }

}
